//
// Created by yearing on 2021/5/25.
//
// 面试题3（二）：不修改数组找出重复的数字
// 题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至
// 少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的
// 数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的
// 输出是重复的数字2或者3。

#include "iostream"
#include "set"
#include "vector"

using namespace std;

vector<int> getduplicateNoEdit(int * data,int leng)
{
    vector<int> t;
    set<int> sdata;
    for (int i = 0; i < leng; ++i) {
        if (sdata.find(data[i]) != sdata.end())
        {
            t.push_back(data[i]);
        } else{
            sdata.insert(data[i]);
        }
    }
   return t;
}
// ====================测试代码====================

void test1()
{
    int numbers[] = { 2, 3, 5, 4, 3, 2, 6, 7 };
    int duplications[] = { 2, 3 };
    vector<int> result = getduplicateNoEdit(numbers,sizeof(numbers) / sizeof(int));
    for (int i = 0; i < result.size(); ++i) {
       cout<< "result: "<< result[i]<<" ";
    }
}
int main()
{
    test1();
    return  0;
}